04 Soliter

U verziji igre “Soliter” igrač dobija promešani špil od n karata iste boje, numerisanih od 1 do n. Cilj igrača je da oformi što duži rastući niz karata, pri čemu sme da koristi pomoćno mesto za odlaganje jedne karte. U svakom potezu igrač bira između tri akcije:

• može da postavi kartu sa vrha špila na kraj rastućeg niza
• može da odloži kartu sa vrha špila na pomoćno mesto
• može da premesti kartu sa pomoćnog mesta na kraj rastućeg niza

Ukoliko igrač ne može da izvede ni jednu od tri akcije, igra se završava.

Ispisati najduži rastući niz koji igrač može da formira od datog špila. Vremenska i prostorna složenost treba da budu O(n).

Ulaz

Sa standardnog ulaza se učitava prirodan broj n, a zatim i permutacija brojeva od 1 do n koja predstavlja špil.

Izlaz

Na standardni izlaz ispisati najduži mogući rastući niz.

Primer

Ulaz

6
4 2 5 3 6 1

Izlaz

2 4 5 6

Igrač može da oformi najduži rastući niz sledećim redom poteza:

• Vuče kartu 4 i stavlja je na pomoćno mesto
• Vuče kartu 2 i stavlja je na početak rastućeg niza
• Prebacuje kartu 4 na kraj rastućeg niza
• Vuče kartu 5 i stavlja je na kraj rastućeg niza
• Vuče kartu 3 i stavlja je na pomoćno mesto
• Vuče kartu 6 i stavlja je na kraj rastućeg niza